package 算法.回溯法.n皇后问题;


import java.util.Scanner;


public class N皇后问题_全排列 {
    public static void main(String[] args) {
        System.out.print("请N皇后问题得N的个数：");
        Scanner scanner = new Scanner(System.in);
        // int max = 8;//max表示n个皇后
        int max = scanner.nextInt();
    //        用array[n]表示皇后在第n+1行,array[n]列,比如array[0] = 8
    //        意思为:该皇后位于第1行第8列的坐标;
        int array[] = new int[max];
        int [] a=new int[max];
        for (int i=0;i<max;i++){
            a[i]=i+1;
        }
       // int[] a = { 8, 2, 3, 4, 5, 6, 7, 1 };
        new N皇后问题_全排列().backtrack(0,max,array,a);
    }
    //核心代码
        public void backtrack(int n,int max,int []array,int []a) {
            if (n == max) {//遍历到叶子节点后退出
                print(array);
                return;
            } else {
                for (int i = n; i < max; i++) {
                   // 更新a数组 swap(a,n,i) (意为 既然已经使用过a[i]那就用原本的a[n]替换a[i]
                    // 保证列值不重复)
                    array[n] = a[i];
                    swap(a, n, i);
                    if (nice(n,array)) {
                        backtrack(n + 1,max,array,a);
                    }
                    swap(a, n, i);
                }
            }

        }

    /**
     * 限制条件，防止皇后的斜边相遇
     */
        public boolean nice(int n,int []array) {
            for (int i = 0; i < n; i++) {
                if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    return false;
                }
            }
            return true;
        }


        public void swap(int[] a, int i, int j) {
            int tem = a[i];
            a[i] = a[j];
            a[j] = tem;
        }

        int k = 0;

        public void print(int []array) {
            ++k;
            System.out.print("第" + k + "种解法:");
            for (int i = 0; i < array.length; i++) {
                System.out.print("("+(i+1)+","+array[i]+")");
               // System.out.print(array[i] + " ");
            }
            System.out.println();
        }





}
